package 剑指offer.demo3;
//https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?

/**
 * 重新构建一个head-tail的链表，让一个cur指针去判断比较连个待合并链表，把正确的值连接到tail上
 */
public class 链表合并 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        //定义边界重新构建链表
        ListNode head = null;
        ListNode tail = null;
        //循环两个链表进行判断
        while (list1 != null && list2 != null){
            //定义一个临时节点用来操作连接
            ListNode cur = null;
            //哪个值小就让哪个把临时节点放成它
            if (list1.val < list2.val){
                cur = list1;
                list1 = list1.next;
            }else {
                cur = list2;
                list2 = list2.next;
            }
            //此时临时节点就是小的值进行连接就好（连接到重新构建的链表上即head-tail）；
            //如果头空说明cur是第一个节点，直接放成头就好了，如果头不是空，连接在后面
            if (head == null){
                head = cur;
                tail = cur;
            }else {
                tail.next = cur;
                tail = tail.next;
            }
        }
        //while走完时，此时必定是有一个链表已经走到头了，把另一个链表插进去就好了
        tail.next = list1 == null ? list2 : list1;
        return head;
    }

    //题目给定链表类
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}
